package NewCoder;

public class BM47 {
    //堆
//    public int findKth(int[] a, int n, int K){
//        // 暂存 第k大的值
//        PriorityQueue<Integer> queue = new PriorityQueue<>(K);
//        // n * 调整 lgk
//        for (int num : a) {
//            if (queue.isEmpty() || num > queue.peek()) {
//                if (queue.size() >= K) {
//                    queue.poll();
//                }
//                queue.add(num);
//            }
//        }
//        return queue.isEmpty() ? 0 : queue.peek();
//    }

    //快排
    public int findKth(int[] a, int n, int K) {
        // write code here
        return quickSort(a,0,n-1,K);

    }
    private int quickSort(int[] a,int i,int j,int k){
        int p=partition(a,i,j);
        if(p-i+1==k){
            return a[p];
        }else if(p-i+1>k){
            return quickSort(a,i,p-1,k);
        }else{
            return quickSort(a,p+1,j,k-(p-i+1));
        }
    }
    private int partition(int[] a,int l,int r){
        int randomIndex=(int)((r-l+1)*Math.random()+l);
        swap(a,l,randomIndex);
        int temp=a[l];
        while(l<r){
            while(l<r && a[r]<=temp){
                r--;
            }
            if(l==r) break;
            else a[l]=a[r];

            while(l<r && a[l]>=temp){
                l++;
            }
            if(l==r) break;
            else a[r]=a[l];
        }
        a[l]=temp;
        return l;
    }
    private void swap(int[] a,int i,int j){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
}
